package com.rr.middle;

/**
 * @author zhuangcanrun
 * @Date 2022/02/08/18:17
 * @description
 **/

/*
 * https://leetcode-cn.com/problems/path-with-maximum-gold/
 * 回溯
 * */
public class GetMaximumGold {
    int[][] grid;
    int row;
    int column;
    int ans = 0;
    int[][] target = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        this.row = grid.length;
        this.column = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] > 0) {
                    justDoIt(i, j, 0);
                }
            }
        }
        return ans;
    }

    private void justDoIt(int i, int j, int sum) {
        sum += grid[i][j];
        ans = Math.max(sum, ans);

        int temp = grid[i][j];
        grid[i][j] = 0;

        for (int[] ints : target) {
            int nextI = i + ints[0];
            int nextJ = j + ints[1];
            if (nextI >= 0 && nextI < row && nextJ >= 0 && nextJ < column && grid[nextI][nextJ] > 0) {
                justDoIt(nextI, nextJ, sum);
            }
        }

        grid[i][j] = temp;
    }
}
